#define ElemType int

#include "common.h"

int** generateMatrix(int n, int* returnSize, int** returnColumnSizes);

int main()
{
	return 0;
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes)
{
	*returnSize = n;
	int* cols_size = calloc(n, sizeof(int*));
	*returnColumnSizes = cols_size;

	int** matrix = calloc(n, sizeof(int*));
	for (int i = 0; i < n; i++) {
		matrix[i] = calloc(n, sizeof(int));
		cols_size[i] = n;
	}

	int num = 1,
		left = 0, right = n - 1, top = 0, bottom = n - 1;
	for (int total_num = n * n; num < total_num;) {
		for (int i = left; i <= right; i++)
			matrix[top][i] = num++;
		top++;
		for (int i = top; i <= bottom; i++)
			matrix[i][right] = num++;
		right--;
		for (int i = right; i >= left; i--)
			matrix[bottom][i] = num++;
		bottom--;
		for (int i = bottom; i >= top; i--)
			matrix[i][left] = num++;
		left++;

	}
	return matrix;
}
